#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool find(TreeNode* root, TreeNode* x)
    {
        if (root == nullptr) return false;
        if (root->val == x->val) return true;
        bool leftfind = find(root->left, x);
        bool rightfind = find(root->right, x);
        return leftfind || rightfind;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if (root == nullptr) return nullptr;
        if (p == root || q == root) return root;
        bool pinleft = find(root->left, p);
        bool pinright = !pinleft;
        bool qinleft = find(root->left, q);
        bool qinright = !qinleft;

        if ((pinleft && qinright) || (pinright && qinleft)) return root;
        else if (pinleft && qinleft) return lowestCommonAncestor(root->left, p, q);
        else return lowestCommonAncestor(root->right, p, q);
    }
};

int main()
{

	return 0;
}